class Solution:
    """
    @param word1: A string
    @param word2: A string
    @return: The minimum number of steps.
    """
    def minDistance(self, word1, word2):
        # write your code here
        len1 = len(word1) + 1
        len2 = len(word2) + 1
        # dis1 = [[0] * len2] * len1 乘法会导致引用
        dis = [[0] * len2 for i in range(len1)]
        for i in range(len1):
            dis[i][0] = i
        for i in range(len2):
            dis[0][i] = i
        for i in range(1, len1):
            for j in range(1, len2):
                if word1[i - 1] == word2[j - 1]:
                    dis[i][j] = dis[i - 1][j - 1]
                else:
                    dis[i][j] = min(dis[i - 1][j - 1], min(dis[i - 1][j], dis[i][j - 1])) + 1
        return dis[-1][-1]